package org.example.Backtracking_algorithm;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class Restore_IP_address {
    public static LinkedList<String> result = new LinkedList<>();
    public static LinkedList<String> value = new LinkedList<>();
    public static void main(String[] args) {
        //复原 IP 地址

        //有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。
        //例如："0.1.2.201" 和 "192.168.1.1" 是 有效 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是 无效 IP 地址。
        //给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 '.' 来形成。你 不能 重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。
        String s = "101023";
        restoreIpAddresses(s);
        for (String s1 : result) {
            System.out.println(s1);
        }
    }
    public static List<String> restoreIpAddresses(String s) {
        get(s,0);
        return result;
    }
    public static void get(String s,int index){
        if (index==s.length() && value.size()==4) {
            //使用StringBuffer对像拼接字符串相较于“+”可以大大减少时间
            StringBuffer sb = new StringBuffer();
            result.add(sb.append(value.get(0)).append(".").append(value.get(1)).append(".").append(value.get(2)).append(".").append(value.get(3)).append(".").toString());
            return;
        }
        if (index>=s.length()) return;
        for (int i = index; i < index+3 && i<s.length(); i++) {
            if (value.size()==4) break;
            if (isIP(s,index,i)){
                value.add(s.substring(index,i+1));
            }else {
                continue;
            }
            get(s,i+1);
            value.removeLast();
        }
    }
    public static boolean isIP(String s,int index,int k){
        if (k-index+1==1) return true;
        return s.charAt(index) != '0' && Integer.parseInt(s.substring(index, k + 1)) <= 255;
    }
}
